/**
	Trie class
	@usage:
	var t:Trie = new Trie(["bla", "bla", "bla", "bla", "bla"]);

	A Trie is a datatype which represents a dictionary of strings.
	It has an initial build time of O(n) and
	an average lookup time of O(log n) due to its n-tree structure
	
	Adapted from Ashley Holtgraver
	
	@author Chandler McWilliams
	@version 2007-01-19
*/
class timber.collection.Trie
{
	private var trie:Object;
	private var ignoreCase;
	

// ===========================================================
// - CONSTRUCTOR
// ===========================================================
	public function Trie(words:Array) {
		trie = {};
		ignoreCase	= false;
		for (var i=0; i<words.length; i++) {
			trie = buildTrieWord(words[i], trie);
		}
	}
	
	public function addWord(word:String):Void {
		trie = buildTrieWord(word, trie);
	}
	
// ===========================================================
// - LOOKUPS
// ===========================================================
	/**
		Return the shortest completion for a string

		@param  str String to search for in the trie
		@return String/false
	*/
	public function getCompletion(str:String) {
		var completion:String = '';
		var depth:Number		 = 0;
		var curr:Object		 = trie;
		var l:Number			 = str.length;
		var char:String;
		var ok:Boolean;
		
		while(true) {
			if (depth == l) return completion + getFirstWordInObject(curr);
		
			char = str.charAt(depth);
			ok = curr[char];
			
			// if not found and we ignore case flip the case
			// this'll slow things down, if you want to avoid it
			// use all one case
			if (!ok && ignoreCase) {
				char = (char.toLowerCase() == char)?char.toUpperCase():char.toLowerCase();
				ok = curr[char];
			}
			
			if (ok) {
				completion += char;
				depth++;
				curr = curr[char];
				continue;
			}
			return false;
		}		
	}
	
	
	/**
		Return all possible completions for a string

		@param  str String to search for in the trie
		@return Array
	*/
	public function getCompletions(str:String):Array {
		var node:Object = getNodeForPrefix(str);
		if (node) {
			return getWordsInObject(node, str);
		}
		
		return null;		
	}
	
	/**
		Search for a prefix in the Trie

		@param  str String to search for
		@return Object
	**/
	public function getNodeForPrefix(str:String):Object {
		var depth:Number		 = 0;
		var curr:Object		 = trie;
		var l:Number			 = str.length;
		var char:String;
		var ok:Boolean;

		while(true) {
			if (depth == l) return curr;
		
			char = str.charAt(depth);
			ok = curr[char];
			
			// if not found and we ignore case flip the case
			// this'll slow things down, if you want to avoid it
			// use all one case
			if (!ok && ignoreCase) {
				char = (char.toLowerCase() == char)?char.toUpperCase():char.toLowerCase();
				ok = curr[char];
			}
			
			if (ok) {
				depth++;
				curr = curr[char];
				continue;
			}
			return null;
		}		
	}
	
	
	// ===========================================================
	// - PRIVATE METHODS FOR CONSTRUCTING AND LOOKUPS
	// ===========================================================
	/**
		Builds a trie structure from a string

		@param  word String word to build the trie for
		@param concat Object to concat the word into
		@return Object
	*/
	private function buildTrieWord(word:String, concat:Object):Object {
		var char:String;
		var localTrie:Object = (!concat)?{}:concat;
		var curr:Object = localTrie;
		for (var i:Number = 0; i<word.length; i++) {
			char = word.charAt(i);
			if (i == (word.length-1)) {
				if (!(curr[char] instanceof Object)) curr[char] = {};
				curr[char].term = true;
				break;
			}
			if (!curr[char]) curr[char] = {};
			curr = curr[char];
		}
		return localTrie;
	}


	/**
		Returns the first word in a trie

		@param  obj trie structure
		@return String
	*/
	private function getFirstWordInObject(obj:Object):String {
		if (obj.term == true) return '';
		var first:String = '';
		for (var i:String in obj) {
			if (i == 'term') continue;
			if (!first) first = i;
			if (obj[i].term == true) return i + getFirstWordInObject(obj[i]);
		}	
		return first + getFirstWordInObject(obj[first]);
	}

	
	/**
		Returns all words in a trie structure

		@param  obj Object t extract words from
		@param str the prefix to prepend to results
		
		@return Array
	*/
	private function getWordsInObject(obj:Object, str:String):Array {
		var words:Array 	= [];
		var i:String;
		
		for (i in obj) {
			if (i == 'term') continue;
			// save it if it's a term
			if (obj[i].term == true) words.push(str+i);
			words = words.concat(getWordsInObject(obj[i], str+i));
		}
		return words;
	}

// ===========================================================
// - ACCESSORS
// ===========================================================
	/**
		Sets if completions should ignore case, default is false

		@param  val boolean for if case should be ignored
		@return Void
	*/
	public function setIgnoresCase(val:Boolean):Void { ignoreCase = val; }

	/**
		Check if the autocompleter ignores case

		@return Boolean
	*/
	public function ignoresCase(Void):Boolean { return ignoreCase; }
	
	/**
		Set the trie data object

		@param  val object formatted as a trie
		@return Void
	**/
	public function setTrieOject(val:Object):Void {
		trie = val;
	}

	/**
		Get the raw trie data object

		@return Object
	**/
	public function getTrieOject(Void):Object {
		return trie;
	}

	public function toString():String {
		return "[timber.collection.Trie]";
	}
}